package com.example.divideandconquer38;


class DivideAndConquer {


    /** 逆序对个数. */
    private int num = 0;

    /**
     * 计数数组 a 中逆序对个数
     * @param a 数组
     * @param n 数组长度
     * @return
     * @author lijiewei
     * @date   2022/1/28 15:58
     */
    public int count(int[] a, int n) {
        num = 0;
        mergeSortCounting(a, 0, n-1);
        return num;
    }

    /**
     * 合并排序
     * @param a 数组
     * @param p 开始节点
     * @param r 结束节点
     * @return
     * @author lijiewei
     * @date   2022/1/28 16:03
     */
    private void mergeSortCounting(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = (p+r)/2;
        mergeSortCounting(a, p, q);
        mergeSortCounting(a, q+1, r);
        merge(a, p, q, r);
    }

    /**
     * 合并数组
     * @param a 数组
     * @param p 开始节点
     * @param q 中间节点
     * @param r 结束节点
     * @return
     * @author lijiewei
     * @date   2022/1/28 16:19
     */
    private void merge(int[] a, int p, int q, int r) {
        int i=p, j=q+1, k=0;

        int[] tmp = new int[r-p+1];
        while (i <= q && j<=r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                //统计p-q之间，比a[j]大的元素
                num += (q-i+1);
                tmp[k++] = a[j++];
            }
        }
        while (i <= q) {
            //处理剩下的
            tmp[k++] = a[i++];
        }
        while (j <= r) {
            //处理剩下的
            tmp[k++] = a[j++];
        }
        for (i = 0; i <= r-p; i++) {
            a[p+i] = tmp[i];
        }
    }
}
